package org.kfive.nova.algorithm.sort;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 14-5-13
 * Time: 上午9:16
 * To change this template use File | Settings | File Templates.
 */
public class QuickSort {

    private static int searchMid(int [] source,int low,int high){
        if(source!=null&&source.length>0){
            int i=low;
            int j =high;
            int temp = source[low];
            while (i<j){
                while (i<j&&source[j]>temp){
                    j--;
                }
                if(i<j){
                    source[i]=source[j];
                    i++;
                }
                while (i<j&&source[i]<temp){
                    i++;
                }
                if(i<j){
                    source[j]=source[i];
                    j--;
                }
            }
            source[i] = temp;
            return i;
        }
        return -1;
    }

    public static void quickSort(int [] source,int low,int high){

        if(low<high){
            int index = searchMid(source,low,high);
            quickSort(source, low, index-1);
            quickSort(source, index+1, high);
        }
    }

    public static void main(String [] args){
        int [] source = {8,3,6,8,1,2,0,4,1,56,78,123,45,98};
        quickSort(source,0,13);
        for (int i=0;i<source.length;i++){
            System.out.println(source[i]);
        }
    }
}
